{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Count Number of Special Subsequences"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: countSpecialSubsequences"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #统计特殊子序列的数目"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p><strong>特殊序列</strong> 是由&nbsp;<strong>正整数</strong>&nbsp;个 <code>0</code>&nbsp;，紧接着&nbsp;<strong>正整数</strong>&nbsp;个 <code>1</code>&nbsp;，最后 <strong>正整数</strong>&nbsp;个 <code>2</code>&nbsp;组成的序列。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>比方说，<code>[0,1,2]</code> 和&nbsp;<code>[0,0,1,1,1,2]</code>&nbsp;是特殊序列。</li>\n",
    "\t<li>相反，<code>[2,1,0]</code>&nbsp;，<code>[1]</code>&nbsp;和&nbsp;<code>[0,1,2,0]</code>&nbsp;就不是特殊序列。</li>\n",
    "</ul>\n",
    "\n",
    "<p>给你一个数组&nbsp;<code>nums</code>&nbsp;（<strong>仅</strong>&nbsp;包含整数&nbsp;<code>0</code>，<code>1</code>&nbsp;和&nbsp;<code>2</code>），请你返回 <b>不同特殊子序列的数目</b>&nbsp;。由于答案可能很大，请你将它对&nbsp;<code>10<sup>9</sup> + 7</code> <strong>取余</strong> 后返回。</p>\n",
    "\n",
    "<p>一个数组的 <strong>子序列</strong>&nbsp;是从原数组中删除零个或者若干个元素后，剩下元素不改变顺序得到的序列。如果两个子序列的 <strong>下标集合</strong>&nbsp;不同，那么这两个子序列是 <strong>不同的</strong>&nbsp;。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>nums = [0,1,2,2]\n",
    "<b>输出：</b>3\n",
    "<b>解释：</b>特殊子序列为 [<strong>0</strong>,<strong>1</strong>,<strong>2</strong>,2]，[<strong>0</strong>,<strong>1</strong>,2,<strong>2</strong>] 和 [<strong>0</strong>,<strong>1</strong>,<strong>2</strong>,<strong>2</strong>] 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>nums = [2,2,0,0]\n",
    "<b>输出：</b>0\n",
    "<b>解释：</b>数组 [2,2,0,0] 中没有特殊子序列。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>nums = [0,1,2,0,1,2]\n",
    "<b>输出：</b>7\n",
    "<b>解释：</b>特殊子序列包括：\n",
    "- [<strong>0</strong>,<strong>1</strong>,<strong>2</strong>,0,1,2]\n",
    "- [<strong>0</strong>,<strong>1</strong>,2,0,1,<strong>2</strong>]\n",
    "- [<strong>0</strong>,<strong>1</strong>,<strong>2</strong>,0,1,<strong>2</strong>]\n",
    "- [<strong>0</strong>,<strong>1</strong>,2,0,<strong>1</strong>,<strong>2</strong>]\n",
    "- [<strong>0</strong>,1,2,<strong>0</strong>,<strong>1</strong>,<strong>2</strong>]\n",
    "- [<strong>0</strong>,1,2,0,<strong>1</strong>,<strong>2</strong>]\n",
    "- [0,1,2,<strong>0</strong>,<strong>1</strong>,<strong>2</strong>]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>0 &lt;= nums[i] &lt;= 2</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [count-number-of-special-subsequences](https://leetcode.cn/problems/count-number-of-special-subsequences/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [count-number-of-special-subsequences](https://leetcode.cn/problems/count-number-of-special-subsequences/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[0,1,2,2]', '[2,2,0,0]', '[0,1,2,0,1,2]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSpecialSubsequences(self, nums: List[int]) -> int:\n",
    "        # 1 - 1   2 - 3 3 - 7 4 - 15\n",
    "        Mod = 10**9+7\n",
    "        # dp 规律15 7 3 1\n",
    "        # nums = [0,1,2,0,1,2]\n",
    "        #        [7,5,3,1,1,1] 正确的\n",
    "        table = [0]*3\n",
    "        res = 0\n",
    "        n = len(nums)\n",
    "        for i in range(n-1,-1,-1):\n",
    "            # 可加 也可以不加 或者是单独一个\n",
    "            if nums[i] == 2:\n",
    "                table[2] = table[2]*2 + 1\n",
    "                table[2] %= Mod\n",
    "            elif nums[i] == 1:\n",
    "                table[1] = table[1]*2 + table[2]\n",
    "                table[1] %= Mod\n",
    "            else:\n",
    "                table[0] = table[0]*2 + table[1]\n",
    "                table[0] %= Mod\n",
    "                res = table[0]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSpecialSubsequences(self, nums: List[int]) -> int:\n",
    "        a0 = a1 = a2 = 0\n",
    "        MOD = 10**9 + 7\n",
    "        for i in range(0, len(nums)):\n",
    "            if nums[i] == 0:\n",
    "                a0 += a0 + 1\n",
    "                a0 %= MOD\n",
    "            if nums[i] == 1:\n",
    "                a1 += a1 + a0\n",
    "                a1 %= MOD\n",
    "            if nums[i] == 2:\n",
    "                a2 += a2 + a1\n",
    "                a2 %= MOD\n",
    "        return a2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSpecialSubsequences(self, nums: List[int]) -> int:\n",
    "        f = [0 for _ in range(3)]\n",
    "        mod = 10 ** 9 + 7\n",
    "        for v in nums:\n",
    "            if v == 0:\n",
    "                f[0] = (f[0]*2 + 1) % mod\n",
    "            elif v == 1:\n",
    "                f[1] = (f[1]*2 + f[0]) % mod\n",
    "            else:\n",
    "                f[2] = (f[2]*2 + f[1]) % mod\n",
    "        return f[2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSpecialSubsequences(self, nums: List[int]) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        f0 = f1 = f2 = 0\n",
    "        for num in nums:\n",
    "            if num == 0:\n",
    "                f0 = (f0 * 2 + 1) % mod\n",
    "            elif num == 1:\n",
    "                f1 = (f1 * 2 + f0) % mod\n",
    "            else:\n",
    "                f2 = (f2 * 2 + f1) % mod\n",
    "        return f2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSpecialSubsequences(self, nums: List[int]) -> int:\n",
    "        mod = 1000000007\n",
    "        n=len(nums)\n",
    "        dp0=0\n",
    "        dp1=0\n",
    "        dp2=1 if nums[-1]==2 else 0\n",
    "        for i in reversed(range(n-1)):\n",
    "            dp0,dp1,dp2 = 2*dp0+dp1 if nums[i]==0 else dp0,2*dp1+dp2 if nums[i]==1 else dp1,2*dp2+1 if nums[i]==2 else dp2\n",
    "            dp0 %= mod\n",
    "            dp1 %= mod\n",
    "            dp2 %= mod\n",
    "        return dp0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSpecialSubsequences(self, nums: List[int]) -> int:\n",
    "\n",
    "        xx0,xx1=0,1\n",
    "        yy0,yy1=0,0\n",
    "        zz0,zz1=0,0\n",
    "        md=1000000007\n",
    "        for k in nums:\n",
    "            if k==0:\n",
    "                xx0+=1\n",
    "                xx1=(xx1*2)%md\n",
    "            elif k==1:\n",
    "                yy0+=1\n",
    "                yy1=((xx1-1)+yy1*2)%md\n",
    "            else:\n",
    "                zz0+=1\n",
    "                zz1=(yy1+2*zz1)%md\n",
    "        return zz1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSpecialSubsequences(self, nums: List[int]) -> int:\n",
    "        dp, mod = [0, 0, 0, 1], 10 ** 9 + 7\n",
    "        for num in nums:\n",
    "            dp[num] = (2 * dp[num] + dp[num - 1]) % mod\n",
    "        return dp[2]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSpecialSubsequences(self, nums: List[int]) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        f0 = f1 = f2 = 0\n",
    "        for num in nums:\n",
    "            if num == 0:\n",
    "                f0 = (f0 * 2 + 1) % mod\n",
    "            elif num == 1:\n",
    "                f1 = (f1 * 2 + f0) % mod\n",
    "            else:\n",
    "                f2 = (f2 * 2 + f1) % mod\n",
    "        return f2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSpecialSubsequences(self, nums: List[int]) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        pre_sum_0 = pre_sum_1 = pre_sum_2 = 0\n",
    "        for x in nums:\n",
    "            if x == 0:\n",
    "                pre_sum_0 += pre_sum_0 + 1\n",
    "                pre_sum_0 %= MOD\n",
    "            elif x == 1:\n",
    "                pre_sum_1 += pre_sum_0 + pre_sum_1\n",
    "                pre_sum_1 %= MOD\n",
    "            else:\n",
    "                pre_sum_2 += pre_sum_1 + pre_sum_2\n",
    "                pre_sum_2 %= MOD\n",
    "        return pre_sum_2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSpecialSubsequences(self, nums: List[int]) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        f0 = f1 = f2 = 0\n",
    "        for num in nums:\n",
    "            if num == 0:\n",
    "                f0 = (f0 * 2 + 1) % mod\n",
    "            elif num == 1:\n",
    "                f1 = (f1 * 2 + f0) % mod\n",
    "            else:\n",
    "                f2 = (f2 * 2 + f1) % mod\n",
    "        return f2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def countSpecialSubsequences(self, nums: List[int]) -> int:\n",
    "        cnt = [0, 0, 0]\n",
    "        MOD = 10**9 + 7\n",
    "        for num in nums:\n",
    "            if num == 0:\n",
    "                cnt[0] = (cnt[0] + cnt[0] + 1) % MOD\n",
    "            elif num == 1:\n",
    "                cnt[1] = (cnt[0] + cnt[1] + cnt[1]) % MOD\n",
    "            elif num == 2:\n",
    "                cnt[2] = (cnt[1] + cnt[2] + cnt[2]) % MOD\n",
    "        return cnt[2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSpecialSubsequences(self, nums: List[int]) -> int:\n",
    "        two = three = 0\n",
    "        one = 0\n",
    "        M = 10 ** 9 + 7\n",
    "        for x in nums:\n",
    "            if x == 0:\n",
    "                one = (2 * one + 1) % M\n",
    "            elif x == 1:\n",
    "                two = (one + two * 2) % M\n",
    "            else:\n",
    "                three = (two + three * 2) % M\n",
    "        return three"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSpecialSubsequences(self, nums: List[int]) -> int:\n",
    "        l=len(nums)\n",
    "        dp0,dp1,dp2=0,0,0\n",
    "        for i in range(l):\n",
    "            if nums[i]==0:\n",
    "                dp0=dp0*2+1\n",
    "                dp0=dp0%1000000007\n",
    "            elif nums[i]==1:\n",
    "                dp1=dp0+dp1*2\n",
    "                dp1 = dp1 % 1000000007\n",
    "            else:\n",
    "                dp2=dp1+dp2*2\n",
    "                dp2 = dp2 % 1000000007\n",
    "        return dp2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSpecialSubsequences(self, nums: List[int]) -> int:\n",
    "        mod = 10**9+7\n",
    "        f0,f1,f2 = 0,0,0\n",
    "        for i in range(0,len(nums)):\n",
    "            if nums[i]==0:\n",
    "                f0 = (2*f0+1)%mod\n",
    "            elif nums[i] == 1:\n",
    "                f1 = (2*f1+f0)%mod\n",
    "            else:\n",
    "                f2 = (2*f2+f1)%mod\n",
    "        return f2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSpecialSubsequences(self, nums: List[int]) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        f0 = f1 = f2 = 0\n",
    "        for num in nums:\n",
    "            if num == 0:\n",
    "                f0 = (f0 * 2 + 1) % mod\n",
    "            elif num == 1:\n",
    "                f1 = (f1 * 2 + f0) % mod\n",
    "            else:\n",
    "                f2 = (f2 * 2 + f1) % mod\n",
    "        return f2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSpecialSubsequences(self, nums: List[int]) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        cnt = [0, 0, 0]\n",
    "        for v in nums:\n",
    "            if v == 0:\n",
    "                cnt[0] = (cnt[0] + 1 + cnt[0]) % mod\n",
    "            elif v == 1:\n",
    "                cnt[1] = (cnt[1] + cnt[0] + cnt[1]) % mod\n",
    "            else:\n",
    "                cnt[2] = (cnt[2] + cnt[1] + cnt[2]) % mod\n",
    "        return cnt[2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "MOD = 10**9 + 7\n",
    "\n",
    "class Solution:\n",
    "    def countSpecialSubsequences(self, nums: List[int]) -> int:\n",
    "        dp0, dp1, dp2 = 0, 0, 0\n",
    "        \n",
    "        for num in nums:\n",
    "            if num == 0:\n",
    "                dp0 = (2 * dp0 + 1) % MOD\n",
    "            elif num == 1:\n",
    "                dp1 = (2 * dp1 + dp0) % MOD\n",
    "            elif num == 2:\n",
    "                dp2 = (2 * dp2 + dp1) % MOD\n",
    "                \n",
    "        return dp2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSpecialSubsequences(self, nums: List[int]) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        f0 = f1 = f2 = 0\n",
    "        for num in nums:\n",
    "            if num == 0:\n",
    "                f0 = (f0 * 2 + 1) % mod\n",
    "            elif num == 1:\n",
    "                f1 = (f1 * 2 + f0) % mod\n",
    "            else:\n",
    "                f2 = (f2 * 2 + f1) % mod\n",
    "        return f2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSpecialSubsequences(self, a: List[int]) -> int:\n",
    "        res, mod = 0, 10**9 + 7\n",
    "        f = [0, 0, 0]\n",
    "        for i, x in enumerate(a):\n",
    "            if x == 0:\n",
    "                f[0] = 2 * f[0] + 1\n",
    "            if x == 1:\n",
    "                f[1] = 2 * f[1] + f[0]\n",
    "            if x == 2:\n",
    "                f[2] = 2 * f[2] + f[1]\n",
    "        return f[2] % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # def countSpecialSubsequences(self, nums: List[int]) -> int:\n",
    "    #     n = len(nums)\n",
    "    #     dp0 = [0] * (n + 1)  # 当前位置之前只有0的特殊子序列数目\n",
    "    #     dp1 = [0] * (n + 1)  # 当前位置之前只有1的特殊子序列数目\n",
    "    #     dp2 = [0] * (n + 1) # 当前位置之前只有2的特殊子序列数目\n",
    "        \n",
    "    #     for i in range(1, n+1):\n",
    "    #         if nums[i-1] == 0:\n",
    "    #             dp0[i] = dp0[i-1] + 1\n",
    "    #         if nums[i-1] == 1:\n",
    "    #             dp1[i] = dp1[i-1] +  dp0[i-1] \n",
    "    #         if nums[i-1] == 2:\n",
    "    #             dp2[i] = dp2[i-1] + dp1[i-1] \n",
    "            \n",
    "    #         dp0[i] = (dp0[i-1] + dp0[i]) %  (int(1e9)+7)\n",
    "    #         dp1[i] = (dp1[i-1] + dp1[i]) % (int(1e9)+7)\n",
    "    #         dp2[i] = (dp2[i-1] + dp2[i]) % (int(1e9)+7)\n",
    "\n",
    "    #     print(dp0, dp1, dp2)\n",
    "    #     # [0, 1, 1, 1, 3, 3, 3] [0, 0, 1, 1, 1, 5, 5] [0, 0, 0, 1, 1, 1, 7]\n",
    "    #     return dp2[-1]\n",
    "\n",
    "\n",
    "    def countSpecialSubsequences(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        dp0 = [0] * (2)  # 当前位置之前只有0的特殊子序列数目\n",
    "        dp1 = [0] * (2)  # 当前位置之前只有1的特殊子序列数目\n",
    "        dp2 = [0] * (2) # 当前位置之前只有2的特殊子序列数目\n",
    "        \n",
    "        for i in range(1, n+1):\n",
    "            dp0[i % 2] = 0\n",
    "            dp1[i % 2] = 0\n",
    "            dp2[i % 2] = 0\n",
    "            if nums[i-1] == 0:\n",
    "                dp0[i % 2] = dp0[(i-1) % 2] + 1\n",
    "            if nums[i-1] == 1:\n",
    "                dp1[i % 2] = dp1[(i-1) % 2] +  dp0[(i-1) % 2] \n",
    "            if nums[i-1] == 2:\n",
    "                dp2[i % 2] = dp2[(i-1) % 2] + dp1[(i-1) % 2] \n",
    "            \n",
    "            dp0[i % 2] = (dp0[(i-1) % 2] + dp0[i % 2]) %  (int(1e9)+7)\n",
    "            dp1[i % 2] = (dp1[(i-1) % 2] + dp1[i % 2]) % (int(1e9)+7)\n",
    "            dp2[i % 2] = (dp2[(i-1) % 2] + dp2[i % 2]) % (int(1e9)+7)\n",
    "\n",
    "            # print(dp0[i % 2], nums[i-1])\n",
    "        return dp2[n  % 2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSpecialSubsequences(self, nums: List[int]) -> int:\n",
    "        dp = [1, 0, 0, 0]\n",
    "        for num in nums:\n",
    "            new_dp = dp[:]\n",
    "            if num == 0:\n",
    "                new_dp[1] += dp[1] + dp[0]\n",
    "            elif num == 1:\n",
    "                new_dp[2] += dp[2] + dp[1]\n",
    "            else:\n",
    "                new_dp[3] += dp[3] + dp[2]\n",
    "            dp = new_dp\n",
    "        return dp[3] % (10 ** 9 + 7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSpecialSubsequences(self, nums: List[int]) -> int:\n",
    "        dp=[0,0,0]\n",
    "        n=len(nums)\n",
    "        res=0\n",
    "        for i in range(n):\n",
    "            if nums[i]==0:\n",
    "                a=dp[0]\n",
    "                dp[0]+=a+1\n",
    "            elif nums[i]==1:\n",
    "                a=dp[1]\n",
    "                dp[1]+=dp[0]+a\n",
    "            else:\n",
    "                b=dp[2]\n",
    "                dp[2]+=dp[1]+b\n",
    "        return dp[2]%(10**9+7)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSpecialSubsequences(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        f0, f1, f2 = 0, 0, 0\n",
    "        for num in nums:\n",
    "            if num == 0:\n",
    "                f0 += f0 + 1 \n",
    "            elif num == 1:\n",
    "                f1 += f0 + f1 \n",
    "            else:\n",
    "                f2 += f1 + f2 \n",
    "        return f2 % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSpecialSubsequences(self, nums: List[int]) -> int:\n",
    "        dp = [0 for _ in range(3)]\n",
    "        for n in nums:\n",
    "            if n == 0:\n",
    "                dp[0] = 2 *dp[0] + 1\n",
    "            elif n == 1:\n",
    "                dp[1] = dp[1] * 2 + dp[0]\n",
    "            else:\n",
    "                dp[2] = dp[2] * 2 + dp[1]\n",
    "        return dp[-1] % 1000000007\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from collections import defaultdict, deque\n",
    "from sortedcontainers import SortedList\n",
    "from functools import lru_cache\n",
    "\n",
    "class Solution:\n",
    "    def countSpecialSubsequences(self, nums: List[int]) -> int:\n",
    "        \"\"\"\n",
    "        :param nums:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        ret =[0]* 3\n",
    "        for k,v in enumerate(nums):\n",
    "            if v == 0:\n",
    "                ret[0] = (ret[0] * 2 + 1) % (10 ** 9 + 7)\n",
    "            elif v == 1:\n",
    "                ret[1] = (ret[1] * 2 + ret[0]) % (10 ** 9 + 7)\n",
    "            elif v == 2:\n",
    "                ret[2] = (ret[2] * 2 + ret[1]) % (10 ** 9 + 7)\n",
    "        return ret[2] % (10 ** 9 + 7)\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSpecialSubsequences(self, nums: List[int]) -> int:\n",
    "        # 0\n",
    "        mod = 10**9 + 7\n",
    "        n = len(nums)\n",
    "        zero = [0] * n\n",
    "        one = [0] * n\n",
    "        two = [0] * n\n",
    "        for i in range(n):\n",
    "            if nums[i] == 0:\n",
    "                zero[i] = (zero[i - 1] + zero[i - 1] + 1) % mod\n",
    "                one[i] = one[i - 1]\n",
    "                two[i] = two[i - 1]\n",
    "            elif nums[i] == 1:\n",
    "                one[i] = (one[i - 1] + zero[i - 1] + one[i - 1]) % mod\n",
    "                zero[i] = zero[i - 1]\n",
    "                two[i] = two[i - 1]\n",
    "            else:\n",
    "                zero[i] = zero[i - 1]\n",
    "                one[i] = one[i - 1]\n",
    "                two[i] = (two[i - 1] + two[i - 1] + one[i - 1]) % mod\n",
    "        return two[n - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "动态规划\n",
    "\n",
    "f[i][j]表示以i结尾的特殊子序列的个数\n",
    "看当前的数字是什么，如果当前数字是2, 那么就可以从前面的1和2转移过来\n",
    "如果当前数字是1，可以从零转移过来\n",
    "如果是零，可以从零转移过来\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def countSpecialSubsequences(self, nums: List[int]) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        n = len(nums)\n",
    "        f = [[0, 0, 0] for _ in range(n + 1)]\n",
    "        for i in range(1, n + 1):\n",
    "            f[i] = f[i - 1]\n",
    "            if nums[i - 1] == 0:\n",
    "                f[i][0] += (f[i - 1][0] + 1) % MOD # 自己开头或者接到上一个零的结尾\n",
    "            else:\n",
    "                f[i][nums[i - 1]] += f[i - 1][nums[i - 1]] + f[i - 1][nums[i - 1] - 1] % MOD # 接到1的结尾或者接到2的结尾\n",
    "        return f[n][2] % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "动态规划\n",
    "\n",
    "f[i][j]表示以i结尾的特殊子序列的个数\n",
    "看当前的数字是什么，如果当前数字是2, 那么就可以从前面的1和2转移过来\n",
    "如果当前数字是1，可以从零转移过来\n",
    "如果是零，可以从零转移过来\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def countSpecialSubsequences(self, nums: List[int]) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        n = len(nums)\n",
    "        f = [[0, 0, 0] for _ in range(n + 1)]\n",
    "        for i in range(1, n + 1):\n",
    "            f[i] = f[i - 1]\n",
    "            if nums[i - 1] == 0:\n",
    "                f[i][0] += (f[i - 1][0] + 1) % MOD # 自己开头或者接到上一个零的结尾\n",
    "            else:\n",
    "                f[i][nums[i - 1]] += f[i - 1][nums[i - 1]] + f[i - 1][nums[i - 1] - 1] % MOD # 接到1的结尾或者接到2的结尾\n",
    "        return f[n][2] % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "动态规划\n",
    "\n",
    "f[i][j]表示以i结尾的特殊子序列的个数\n",
    "看当前的数字是什么，如果当前数字是2, 那么就可以从前面的1和2转移过来\n",
    "如果当前数字是1，可以从零转移过来\n",
    "如果是零，可以从零转移过来\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def countSpecialSubsequences(self, nums: List[int]) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        n = len(nums)\n",
    "        f = [[0, 0, 0] for _ in range(n + 1)]\n",
    "        for i in range(1, n + 1):\n",
    "            f[i] = f[i - 1]\n",
    "            if nums[i - 1] == 0:\n",
    "                f[i][0] += f[i - 1][0] + 1 # 自己开头或者接到上一个零的结尾\n",
    "            if nums[i - 1] == 1:\n",
    "                f[i][1] += f[i - 1][1] + f[i - 1][0] # 接到零的结尾或者接到1的结尾\n",
    "            if nums[i - 1] == 2:\n",
    "                f[i][2] += f[i - 1][1] + f[i - 1][2] # 接到1的结尾或者接到2的结尾\n",
    "        return f[n][2] % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSpecialSubsequences(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        dp0 = [0] * n  # 当前位置之前只有0的特殊子序列数目\n",
    "        dp1 = [0] * n  # 当前位置之前只有1的特殊子序列数目\n",
    "        dp2 = [0] * n  # 当前位置之前只有2的特殊子序列数目\n",
    "        \n",
    "        for i in range(n):\n",
    "            if nums[i] == 0:\n",
    "                dp0[i] = dp0[i-1] + 1 if i-1 >=0 else 1\n",
    "            dp0[i] += dp0[i-1] if i-1 >= 0 else 0\n",
    "\n",
    "            dp0[i] = dp0[i] % (int(1e9)+7)\n",
    "\n",
    "            if nums[i] == 1:\n",
    "                dp1[i] = dp1[i-1] +  dp0[i-1] if i-1 >= 0 else 0\n",
    "            dp1[i] += dp1[i-1] \n",
    "            dp1[i] = dp1[i] % (int(1e9)+7)\n",
    "\n",
    "            if nums[i] == 2:\n",
    "                dp2[i] = dp2[i-1] + dp1[i-1] if i-1 >= 0 else 0\n",
    "            dp2[i] += dp2[i-1]\n",
    "            dp2[i] = dp2[i] % (int(1e9)+7)\n",
    "        # print(dp0, dp1, dp2)\n",
    "        return dp2[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSpecialSubsequences(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        dp0 = [0] * (n + 1)  # 当前位置之前只有0的特殊子序列数目\n",
    "        dp1 = [0] * (n + 1)  # 当前位置之前只有1的特殊子序列数目\n",
    "        dp2 = [0] * (n + 1) # 当前位置之前只有2的特殊子序列数目\n",
    "        \n",
    "        for i in range(1, n+1):\n",
    "            if nums[i-1] == 0:\n",
    "                dp0[i] = dp0[i-1] + 1\n",
    "\n",
    "            if nums[i-1] == 1:\n",
    "                dp1[i] = dp1[i-1] +  dp0[i-1] \n",
    "\n",
    "            if nums[i-1] == 2:\n",
    "                dp2[i] = dp2[i-1] + dp1[i-1] \n",
    "            \n",
    "            dp0[i] = (dp0[i-1] + dp0[i]) %  (int(1e9)+7)\n",
    "            dp1[i] = (dp1[i-1] + dp1[i]) % (int(1e9)+7)\n",
    "            dp2[i] = (dp2[i-1] + dp2[i]) % (int(1e9)+7)\n",
    "\n",
    "        # print(dp0, dp1, dp2)\n",
    "        return dp2[-1]\n",
    "\n",
    "\n",
    "    # def countSpecialSubsequences(self, nums: List[int]) -> int:\n",
    "    #     n = len(nums)\n",
    "    #     dp0 = [0] * (n + 1)  # 当前位置之前只有0的特殊子序列数目\n",
    "    #     dp1 = [0] * (n + 1)  # 当前位置之前只有1的特殊子序列数目\n",
    "    #     dp2 = [0] * (n + 1) # 当前位置之前只有2的特殊子序列数目\n",
    "        \n",
    "    #     for i in range(1, n+1):\n",
    "    #         if nums[i-1] == 0:\n",
    "    #             dp0[i] = dp0[i-1] + 1\n",
    "    #         dp0[i] += dp0[i-1]\n",
    "    #         dp0[i] = dp0[i] % (int(1e9)+7)\n",
    "\n",
    "    #         if nums[i-1] == 1:\n",
    "    #             dp1[i] = dp1[i-1] +  dp0[i-1] \n",
    "    #         dp1[i] += dp1[i-1]\n",
    "    #         dp1[i] = dp1[i] % (int(1e9)+7)\n",
    "\n",
    "    #         if nums[i-1] == 2:\n",
    "    #             dp2[i] = dp2[i-1] + dp1[i-1] \n",
    "    #         dp2[i] += dp2[i-1] \n",
    "    #         dp2[i] = dp2[i] % (int(1e9)+7)\n",
    "    #     # print(dp0, dp1, dp2)\n",
    "    #     return dp2[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSpecialSubsequences(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        dp0 = [0] * (n + 1)  # 当前位置之前只有0的特殊子序列数目\n",
    "        dp1 = [0] * (n + 1)  # 当前位置之前只有1的特殊子序列数目\n",
    "        dp2 = [0] * (n + 1) # 当前位置之前只有2的特殊子序列数目\n",
    "        \n",
    "        for i in range(1, n+1):\n",
    "            if nums[i-1] == 0:\n",
    "                dp0[i] = dp0[i-1] + 1\n",
    "            dp0[i] += dp0[i-1]\n",
    "            dp0[i] = dp0[i] % (int(1e9)+7)\n",
    "\n",
    "            if nums[i-1] == 1:\n",
    "                dp1[i] = dp1[i-1] +  dp0[i-1] \n",
    "            dp1[i] += dp1[i-1]\n",
    "            dp1[i] = dp1[i] % (int(1e9)+7)\n",
    "\n",
    "            if nums[i-1] == 2:\n",
    "                dp2[i] = dp2[i-1] + dp1[i-1] \n",
    "            dp2[i] += dp2[i-1] \n",
    "            dp2[i] = dp2[i] % (int(1e9)+7)\n",
    "        # print(dp0, dp1, dp2)\n",
    "        return dp2[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSpecialSubsequences(self, nums: List[int]) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        dp2 = [0 for _ in range(len(nums)+1)]\n",
    "        dp1 = [0 for _ in range(len(nums)+1)]\n",
    "        dp0 = [0 for _ in range(len(nums)+1)]\n",
    "\n",
    "        for i in range(1, len(nums)+1):\n",
    "            if nums[i-1] == 0:\n",
    "                dp0[i] = (2 *  dp0[i-1] + 1) % mod\n",
    "            else:\n",
    "                dp0[i] = (dp0[i-1]) % mod\n",
    "        for i in range(1, len(nums)+1):\n",
    "            if nums[i-1] == 1:\n",
    "                dp1[i] = (2 * dp1[i-1] + dp0[i-1]) % mod\n",
    "            else:\n",
    "                dp1[i] = (dp1[i-1]) % mod\n",
    "        for i in range(1, len(nums)+1):\n",
    "            if nums[i-1] == 2:\n",
    "                dp2[i] = (2 * dp2[i-1] + dp1[i-1]) % mod\n",
    "            else:\n",
    "                dp2[i] = (dp2[i-1]) % mod\n",
    "        # print(dp0)\n",
    "        # print(dp1)\n",
    "        # print(dp2)\n",
    "        return dp2[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSpecialSubsequences(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        dp0 = [0] * n  # 当前位置之前只有0的特殊子序列数目\n",
    "        dp1 = [0] * n  # 当前位置之前只有1的特殊子序列数目\n",
    "        dp2 = [0] * n  # 当前位置之前只有2的特殊子序列数目\n",
    "        \n",
    "        for i in range(n):\n",
    "            if nums[i] == 0:\n",
    "                dp0[i] += 1\n",
    "                if i-1 >=0:\n",
    "                    dp0[i] += dp0[i-1]\n",
    "            dp0[i] += dp0[i-1] if i-1 >= 0 else 0\n",
    "\n",
    "            dp0[i] = dp0[i] % (int(1e9)+7)\n",
    "        for i in range(1, n):\n",
    "            if nums[i] == 1:\n",
    "                dp1[i] += dp1[i-1] +  dp0[i-1]\n",
    "            dp1[i] += dp1[i-1]\n",
    "            dp1[i] = dp1[i] % (int(1e9)+7)\n",
    "        for i in range(2, n):\n",
    "            if nums[i] == 2:\n",
    "                dp2[i] += dp2[i-1] + dp1[i-1]\n",
    "            dp2[i] += dp2[i-1]\n",
    "            dp2[i] = dp2[i] % (int(1e9)+7)\n",
    "        # print(dp0, dp1, dp2)\n",
    "        return dp2[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSpecialSubsequences(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        mod = 10 ** 9 + 7\n",
    "        dp = [[0,0,0] for _ in range(n)]\n",
    "\n",
    "        for i , num in enumerate(nums):\n",
    "            if num == 0:\n",
    "                dp[i][0] = (2 * dp[i-1][0] + 1)%mod\n",
    "                dp[i][1] = dp[i-1][1]\n",
    "                dp[i][2] = dp[i-1][2]\n",
    "            elif num == 1:\n",
    "                dp[i][1] = (2 * dp[i-1][1] + dp[i-1][0])%mod\n",
    "                dp[i][0] = dp[i-1][0]\n",
    "                dp[i][2] = dp[i-1][2]\n",
    "            else:\n",
    "                dp[i][2] = (2 * dp[i-1][2] + dp[i-1][1])%mod\n",
    "                dp[i][1] = dp[i-1][1]\n",
    "                dp[i][0] = dp[i-1][0]\n",
    "        return dp[n-1][2] % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSpecialSubsequences(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [[0]*3 for _ in range(n+1)]\n",
    "        Mod = 10**9+7\n",
    "        for i in range(1,n+1):\n",
    "            if nums[i-1] == 0:\n",
    "                dp[i][0]=(1+dp[i-1][0] + dp[i-1][0])%Mod\n",
    "                dp[i][1] = dp[i-1][1]\n",
    "                dp[i][2] = dp[i-1][2]\n",
    "            elif nums[i-1] == 1:\n",
    "                dp[i][1] =(dp[i-1][1] + dp[i-1][1]+dp[i-1][0])%Mod\n",
    "                dp[i][0] = dp[i-1][0]\n",
    "                dp[i][2] = dp[i-1][2]\n",
    "            else:\n",
    "                dp[i][0] = dp[i-1][0]\n",
    "                dp[i][1] = dp[i-1][1]\n",
    "                dp[i][2] = (dp[i-1][2] + dp[i-1][2] + dp[i-1][1])%Mod\n",
    "        return dp[-1][-1]%Mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSpecialSubsequences(self, nums: List[int]) -> int:\n",
    "        dp = [[0] * 3 for _ in range(len(nums) + 1)]\n",
    "        res = 0\n",
    "        for i in range(len(nums)):\n",
    "            for x in range(3):\n",
    "                dp[i + 1][x] = dp[i][x]\n",
    "            if nums[i] == 0:\n",
    "                dp[i + 1][nums[i]] += 1\n",
    "            dp[i + 1][nums[i]] += dp[i][nums[i]]                \n",
    "            if nums[i] >= 1:\n",
    "                dp[i + 1][nums[i]] += dp[i][nums[i] - 1]\n",
    "            dp[i + 1][nums[i]] %= int(1e9 + 7)                                \n",
    "        return dp[-1][2]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSpecialSubsequences(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        mod = 10 ** 9 + 7\n",
    "        dp = [[0,0,0] for _ in range(n)]\n",
    "\n",
    "        for i , num in enumerate(nums):\n",
    "            dp[i] = deepcopy(dp[i-1])\n",
    "            if num == 0:\n",
    "                dp[i][0] = (2 * dp[i-1][0] + 1)%mod\n",
    "            elif num == 1:\n",
    "                dp[i][1] = (2 * dp[i-1][1] + dp[i-1][0])%mod\n",
    "            else:\n",
    "                dp[i][2] = (2 * dp[i-1][2] + dp[i-1][1])%mod\n",
    "        return dp[n-1][2] % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "Mod = (10 ** 9 + 7)\n",
    "class Solution:\n",
    "    def countSpecialSubsequences(self, nums: List[int]) -> int:\n",
    "        f0 = 0\n",
    "        f01 = 0\n",
    "        f012 = 0\n",
    "        for num in nums:\n",
    "            if num == 2:\n",
    "                f012 += f012+f01\n",
    "                f012 %= Mod\n",
    "            elif num == 1:\n",
    "                f01 += f01+f0\n",
    "                f01 %= Mod\n",
    "            else:\n",
    "                f0 += f0 + 1\n",
    "                f0 %= Mod\n",
    "        return f012 % Mod\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "\n",
    "class Solution:\n",
    "    def countSpecialSubsequences(self, nums: List[int]) -> int:\n",
    "        f0 = 0\n",
    "        f01 = 0\n",
    "        f012 = 0\n",
    "        for num in nums:\n",
    "            if num == 2:\n",
    "                f012 += f012+f01\n",
    "            elif num == 1:\n",
    "                f01 += f01+f0\n",
    "            else:\n",
    "                f0 += f0 + 1\n",
    "        return f012 % (10 ** 9 + 7)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSpecialSubsequences(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        mod = 10 ** 9 + 7\n",
    "        dp = [[0] * 3 for _ in range(n)]\n",
    "        dp[0][0] = nums[0] == 0\n",
    "        for i in range(1, n):\n",
    "            dp[i][0] = (dp[i-1][0] + (nums[i] == 0) * (dp[i-1][0] + 1)) % mod\n",
    "            dp[i][1] = (dp[i-1][1] + (nums[i] == 1) * (dp[i-1][0] + dp[i-1][1])) % mod\n",
    "            dp[i][2] = (dp[i-1][2] + (nums[i] == 2) * (dp[i-1][1] + dp[i-1][2])) % mod\n",
    "        return dp[n-1][2] % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSpecialSubsequences(self, nums: List[int]) -> int:\n",
    "\n",
    "        n = len(nums)\n",
    "        dp = [[0]*3 for _ in range(n+1)]\n",
    "        MODX = 10**9+7\n",
    "        for i in range(n):\n",
    "            if nums[i]==0:\n",
    "                dp[i+1][0] = 2*dp[i][0]+1\n",
    "                dp[i+1][1] = dp[i][1]\n",
    "                dp[i+1][2] = dp[i][2]\n",
    "\n",
    "            elif nums[i]==1:\n",
    "                dp[i+1][0] = dp[i][0]\n",
    "                dp[i+1][1] = dp[i][1]+dp[i][1]+dp[i][0]\n",
    "                dp[i+1][2] = dp[i][2]\n",
    "            \n",
    "            elif nums[i]==2:\n",
    "                dp[i+1][0] = dp[i][0]\n",
    "                dp[i+1][1] = dp[i][1]\n",
    "                dp[i+1][2] = dp[i][2]+dp[i][2]+dp[i][1]\n",
    "\n",
    "            for j in range(3):\n",
    "                dp[i+1][j] %= MODX\n",
    "        return dp[n][2]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import *\n",
    "from math import *\n",
    "from functools import cache,lru_cache\n",
    "from queue import *\n",
    "from heapq import *\n",
    "from itertools import *\n",
    "from bisect import bisect_left\n",
    "# start-----------------------------------------------------\n",
    "class Solution:\n",
    "    def countSpecialSubsequences(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [[0] * 3 for _ in range(n+1)]\n",
    "        ans,mod = 0, int(1e9+7)\n",
    "        for i in range(1, n+1):\n",
    "            z = nums[i-1]\n",
    "            dp[i][0],dp[i][1],dp[i][2] = dp[i-1][0] % mod,dp[i-1][1] % mod,dp[i-1][2] % mod\n",
    "            if z == 0:\n",
    "                dp[i][0] += dp[i-1][0] + 1\n",
    "            elif z == 1:\n",
    "                dp[i][1] += dp[i-1][0] + dp[i-1][1]\n",
    "            else:\n",
    "                dp[i][2] += dp[i-1][1] + dp[i-1][2]\n",
    "        return dp[-1][-1] % mod\n",
    "# end-------------------------------------------------------\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSpecialSubsequences(self, nums: List[int]) -> int:\n",
    "       def dfs(i: int, j: int) -> int:\n",
    "          if i == n:\n",
    "             return j == 2\n",
    "          if memo[i][j] != -1:\n",
    "             return memo[i][j]\n",
    "          res = dfs(i + 1, j)\n",
    "          if nums[i] - j == 1 or nums[i] - j == 0:\n",
    "             res += dfs(i + 1, nums[i])\n",
    "          res %= MOD\n",
    "          memo[i][j] = res\n",
    "          return res\n",
    "       n = len(nums)\n",
    "       MOD = 10 ** 9 + 7\n",
    "       memo = [[-1] * 3 for _ in range(n)]\n",
    "       res = 0\n",
    "       for i in range(n):\n",
    "          if nums[i] == 0:\n",
    "             res += dfs(i + 1, 0)\n",
    "             res %= MOD\n",
    "       return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "kmod = 10**9 + 7\n",
    "class Solution:\n",
    "    def countSpecialSubsequences(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(idx, pre):\n",
    "            if idx == n:\n",
    "                return pre == 2\n",
    "            \n",
    "            if nums[idx] < pre:\n",
    "                return dfs(idx + 1, pre)\n",
    "            elif nums[idx] == pre:\n",
    "                return (dfs(idx + 1, pre) * 2) % kmod\n",
    "            else:\n",
    "                if nums[idx] - pre == 1:\n",
    "                    return (dfs(idx + 1, pre) + dfs(idx + 1, nums[idx])) % kmod\n",
    "                return dfs(idx + 1, pre)\n",
    "\n",
    "        ans = dfs(0, -1)\n",
    "        dfs.cache_clear()\n",
    "        return ans % kmod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSpecialSubsequences(self, nums: List[int]) -> int:\n",
    "        mod = 10**9+7   \n",
    "        n = len(nums)\n",
    "        vis = [[-1]*3 for i in range(n)]\n",
    "        @cache\n",
    "        def dfs(i, j):\n",
    "            # i，n的元素，组成类型为j的子序列的数目\n",
    "            if vis[i][j] != -1:\n",
    "                return vis[i][j]\n",
    "            if i == -1:\n",
    "                return 0\n",
    "            res = 0\n",
    "            if nums[i] != j:\n",
    "                return dfs(i-1, j)\n",
    "            if nums[i] == 0:\n",
    "                res += 2*dfs(i-1, 0) + 1\n",
    "            if nums[i] == 1:\n",
    "                res += 2*dfs(i-1, 1) + dfs(i-1, 0) # 选这个1\n",
    "            if nums[i] == 2:\n",
    "                res += dfs(i-1, 1) + 2*dfs(i-1, 2) # 选这个2\n",
    "            vis[i][j] = res \n",
    "            return res % mod            \n",
    "        \n",
    "        return dfs(n-1, 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSpecialSubsequences(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        mod = 10 ** 9 + 7\n",
    "        dp = [[0,0,0] for _ in range(n)]\n",
    "\n",
    "        for i , num in enumerate(nums):\n",
    "            dp[i] = deepcopy(dp[i-1])\n",
    "            if num == 0:\n",
    "                dp[i][0] = 2 * dp[i-1][0] + 1\n",
    "            elif num == 1:\n",
    "                dp[i][1] = 2 * dp[i-1][1] + dp[i-1][0]\n",
    "            else:\n",
    "                dp[i][2] = 2 * dp[i-1][2] + dp[i-1][1]\n",
    "        return dp[n-1][2] % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSpecialSubsequences(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [[0,0,0] for _ in range(n)]\n",
    "        mod = 10 ** 9 + 7\n",
    "        for i , num in enumerate(nums):\n",
    "            if num == 0:\n",
    "                dp[i][0] = dp[i-1][0] * 2 + 1\n",
    "                dp[i][1] = dp[i-1][1]\n",
    "                dp[i][2] = dp[i-1][2]\n",
    "            elif num == 1:\n",
    "                dp[i][0] = dp[i-1][0] \n",
    "                dp[i][1] = dp[i-1][1] * 2 + dp[i-1][0]\n",
    "                dp[i][2] = dp[i-1][2]\n",
    "            else:\n",
    "                dp[i][0] = dp[i-1][0]\n",
    "                dp[i][1] = dp[i-1][1]\n",
    "                dp[i][2] = dp[i-1][2] * 2 + dp[i-1][1]\n",
    "        return dp[n-1][2] % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSpecialSubsequences(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        f = [[0] * 3 for _ in range(n)]\n",
    "        for i, x in enumerate(nums):\n",
    "            f[i][0] = f[i - 1][0]\n",
    "            f[i][1] = f[i - 1][1]\n",
    "            f[i][2] = f[i - 1][2]\n",
    "            if x == 0:\n",
    "                f[i][0] = 2 * f[i - 1][0] + 1\n",
    "            elif x == 1:\n",
    "                f[i][1] = 2 * f[i - 1][1] + f[i - 1][0]\n",
    "            else:\n",
    "                f[i][2] = 2 * f[i - 1][2] + f[i - 1][1]\n",
    "        return f[-1][2] % (10**9 + 7)\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
